package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1520. 最多的不重叠子字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/9 9:37
 */
public class MaxNumOfSubstrings {

    public static void main(String[] args) {
        MaxNumOfSubstrings test = new MaxNumOfSubstrings();

        // ["e","f","ccc"]
//        String str = "adefaddaccc";

        // ["d","bb","cc"]
//        String str = "abbaccd";

        //
        String str = Utils.getStr(100, 'a', 'g')
                + Utils.getStr(100, 'h', 'n')
                + Utils.getStr(100, 'o', 't')
                + Utils.getStr(100, 'u', 'z');

        System.out.println(str);
        List<String> list = test.maxNumOfSubstrings(str);
        System.out.println(list);
    }

    public List<String> maxNumOfSubstrings(String s) {
        TreeSet<Integer>[] sets = new TreeSet[26];
        for (int i = 0; i < 26; i++) {
            sets[i] = new TreeSet<>();
        }
        int length = s.length();
        for (int i = 0; i < length; i++) {
            int index = s.charAt(i) - 'a';
            sets[index].add(i);
        }
        int[] flags = new int[26];
        Set<Long> f = new HashSet<>();
        for (int i = 0; i < 26; i++) {
            Arrays.fill(flags, 0);
            TreeSet<Integer> set = sets[i];
            if (set.isEmpty()) {
                continue;
            }
            long first = set.first();
            long value = find((first << 32) + set.last(), flags, sets);
            if (f.contains(value)) {
                continue;
            }
            f.add(value);
        }
        int size = f.size();
        int[][] arr = new int[size][3];
        int i = 0;
        for (long value : f) {
            arr[i][0] = (int) (value >> 32);
            arr[i][1] = (int) value;
            i++;
        }
        Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
        List<String> list = new ArrayList<>();
        list.add(s.substring(arr[0][0], arr[0][1] + 1));
        for (int j = 1; j < size; j++) {
            int st = arr[j][0];
            int end = arr[j - 1][1];
            if (end > st) {
                list.remove(list.size() - 1);
            }
            list.add(s.substring(st, arr[j][1] + 1));
        }
        return list;
    }

    private long find(long value, int[] flags, TreeSet<Integer>[] sets) {
        int st = (int) (value >> 32);
        int end = (int) value;
        boolean f = false;
        for (int i = 0; i < 26; i++) {
            if (flags[i] == 1) {
                continue;
            }
            TreeSet<Integer> set = sets[i];
            if (set.isEmpty()) {
                flags[i] = 1;
                continue;
            }
            Integer first = set.first();
            Integer last = set.last();
            Integer ceiling = set.ceiling(st);
            Integer floor = set.floor(end);
            if ((ceiling != null && ceiling < end) || (floor != null && floor > st)) {
                if (first < st) {
                    st = first;
                    f = true;
                }
                if (last > end) {
                    end = last;
                    f = true;
                }
            }
            if (first >= st && last <= end) {
                flags[i] = 1;
            }
        }
        if (f) {
            return find(((long) st << 32) + end, flags, sets);
        }
        return ((long) st << 32) + end;
    }
}
